10652. The unique topological sort

 

An unweighted directed graph is given. Determine whether it has a unique topological sort.

 

Input. The first line contains the number of vertices n (1 ≤ n ≤ 2 * 105) and the number of edges m (1 ≤ m ≤ 105) in the graph. The following m lines describe the edges of the graph, each represented by a pair of integers – the indices of the start and end vertices.

 

Output. Print “YES” if there is a unique topological sort of the vertices, and “NO” if there are multiple valid sorts. If a topological sort is impossible, print -1.

 

Sample input 1

Sample output 1

3 2

1 2

2 3

YES

 

 

Sample input 2

Sample output 2

3 2

1 2

1 3

NO

 

 

SOLUTION

graphs – topological sort

 

Algorithm analysis

Let’s run Kahn’s algorithm. If at each iteration the queue always contains exactly one vertex, then the topological sort is unique.

 

Example

The graphs from the test cases are as follows:

In the first sample the topological sort is unique:

·        1, 2, 3.

In the second sample there are two possible topological sorts:

·        1, 2, 3;

·        1, 3, 2;

 

Algorithm implementation

Store the input graph in an adjacency list g. The in-degrees of the vertices are stored in the array InDegree. Declare the queue q.

 

vector<vector<int> > g;

vector<int> InDegree;

deque<int> q;

 

Read the input graph. For each edge (a, b) increment InDegree[b] by 1.

 

scanf("%d %d", &n, &m);

g.resize(n + 1);

InDegree.resize(n + 1);

for (i = 0; i < m; i++)

{

  scanf("%d %d", &a, &b);

  g[a].push_back(b);

  InDegree[b]++;

}

 

All vertices with an in-degree of zero add to the queue q.

 

for (i = 1; i < InDegree.size(); i++)

  if (!InDegree[i]) q.push_back(i);

 

Set flag = 1 if the topological sort is unique.

 

flag = 1;

 

Continue the algorithm while the queue q is not empty.

 

while (!q.empty())

{

 

If the queue contains more than one vertex, then the topological sort is not unique.

 

  if (q.size() > 1) flag = 0;

 

Pop the current vertex v from the queue.

 

  v = q.front(); q.pop_front();

 

Remove the edges (v, to) from the graph. For each such edge, decrease the in-degree of vertex to. If the in-degree of vertex to becomes zero, add it to the queue.

 

  for (int to : g[v])

  {

    InDegree[to]--;

    if (!InDegree[to]) q.push_back(to);

  }

}

 

Depending on the value of flag, print the answer.

 

if (flag == 1)

  printf("YES\n");

else

  printf("NO\n");